|
Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal interest in the output. In those situations, the agents might not report the input truthfully because of their own personal interests. On top of the usual requirements in classical algorithm design, say ''polynomial-time running time'', ''good approximation ratio'', ... the designer must also care about incentive constraints. We can see Algorithmic Game Theory from two perspectives: * ''Analysis'': look at the current implemented algorithms and analyze them using Game Theory tools: calculate and prove properties on their Nash equilibria, price of anarchy, best-response dynamics ... * ''Design'': design games that have both good game-theoretical and algorithmic properties. This area is called algorithmic mechanism design The field was started when Nisan and Ronen in STOC'99 〔.〕 drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract: ==The Internet as a catalyst== The Internet created a new economy—both as a foundation for exchange and commerce, and in its own right. The computational nature of the Internet allowed for the use of computational tools in this new emerging economy. On the other hand, the Internet itself is the outcome of actions of many. This was new to the classic, ‘top-down’ approach to computation that held till then. Thus, game theory is a natural way to view the Internet and interactions within it, both human and mechanical. Game theory studies equilibria (such as the Nash equilibrium). An equilibrium is generally defined as a state in which no player has an incentive to change their strategy. Equilibria are found in several fields related to the Internet, for instance financial interactions and communication load-balancing. Game theory provides tools to analyze equilibria, and a common approach is then to ‘find the game’—that is, to formalize specific Internet interactions as a game, and to derive the associated equilibria. Rephrasing problems in terms of games allows the analysis of Internet-based interactions and the construction of mechanisms to meet specified demands. If equilibria can be shown to exist, a further question must be answered: can an equilibrium be found, and in reasonable time? This leads to the analysis of algorithms for finding equilibria. Of special importance is the complexity class PPAD, which includes many problems in algorithmic game theory. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Algorithmic game theory」の詳細全文を読む スポンサード リンク
|